// https://www.lintcode.com/problem/gas-station/

public class Solution {
  /**
    * @param gas: An array of integers
    * @param cost: An array of integers
    * @return: An integer
    */
  public int canCompleteCircuit(int[] gas, int[] cost) {
    // write your code here
    int i = 0;
    int len = gas.length;
    while (i < len) { // 遍历所有的加油站，并从该加油站开始！
      int j = i; // 从i点出发
      int cnt = 1; // 经历过的点
      int gasVol = 0; // 初始油量
      while (cnt <= len) {
        if (gasVol + gas[j % len] >= cost[j % len]) { // 可以加油到下一个点
          if (cnt == len) {
            return i;
          }
          gasVol += gas[j % len] - cost[j % len];
          ++j;
          ++cnt;
        } else {
          i = j + 1; // 这个点不行，换下个点开始。
          break;
        }
      }
    }
    return -1;
  }
}